package DoExercise.HSP_ZCY.A016_动态规划;

/**
 * @Author: Du
 * @Date: 2021/7/23 17:22
 * <p>
 * 从左往右的尝试模型
 */
public class Code10_将数字转化为字符
{
    public static void main(String[] args)
    {
        System.out.println(dpWays("11111"));
    }
    
    /**
     * 通过动态规划的方法解决该问题
     *
     * @param s
     * @return
     */
    public static int dpWays(String s)
    {
        if (s == null || s.length() == 0)
        {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--)
        {
            if (str[i] == '0')
            {
                dp[i] = 0;
            } else if (str[i] == '1')
            {
                dp[i] = dp[i + 1];
                if (i + 1 < N)
                {
                    dp[i] += dp[i + 2];
                }
            } else if (str[i] == '2')
            {
                dp[i] = dp[i + 1];
                if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6'))
                {
                    dp[i] += dp[i + 2];
                }
            } else
            {
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }
}
